package arr;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * @author kaho
 * @since 2021/2/20
 */
public class _697_数组的度 {

    /**
     * 给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
     * <p>
     * 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/degree-of-an-array
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @return
     */
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Integer> left = new HashMap<>();
        Map<Integer, Integer> right = new HashMap<>();

        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            int count = map.getOrDefault(nums[i], 0)+1;
            map.put(nums[i], count);
            max = Math.max(max, count);
            if (!left.containsKey(nums[i])) {
                left.put(nums[i],i);
            }
            right.put(nums[i],i);
        }
        int min = nums.length;

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue().equals(max)) {
                int r = right.get(entry.getKey()) - left.get(entry.getKey()) + 1;
                min = Math.min(min, r);
            }
        }
        return min;
    }

    public static void main(String[] args) {

    }
}
